Electronic messages are normally transmitted between remote correspondents via a communications system typically including a network of interconnected computers. Such messages are readily intercepted and viewed by others using the network. Thus, correspondents desiring privacy may encrypt or encode a message in a way that only the recipient can decrypt or decode it to view the message contents. A common encryption technique is disclosed in U.S. Pat. No. 4,405,829 to Rivest et al., which is incorporated by reference. The technique is also known as the RSA technique.
Rivest discloses a "public key" technique in which each user desiring to receive encrypted messages creates a numerical encoding key that may be mathematically applied by a sender to an original message to encode the message. The recipient also creates and maintains secretly a decoding key that, when mathematically applied to the encoded message, decodes it to regenerate the original message. Each encoding key includes the product of two large prime numbers. These two prime factors can not be determined from their product without extraordinary computation efforts. The secret decoding key is also derived from the same two secret prime numbers. Each recipient posts his or her own encoding key in a public repository so that all correspondents wishing to send confidential messages to that recipient may use that recipient's key to encode messages. The public key repository is like a telephone directory, in that it enables anyone to look up a listed individual and obtain a number required for communication. Because of the difficulty of factoring the prime factors in a public encoding key, the decoding key remains secure to a degree.
The difficulty of deriving the secret decoding key from a public encoding key varies with the size of the key. With modest computing power, a small product of two primes may be factored by attempting to divide it by each successive prime number until division occurs without a remainder. Larger numbers require more sophisticated techniques, and as a general rule, factorization is more difficult with larger numbers. Using current technology, a public key to expressed as a string of 512 binary "one" or "zero" bits will require several thousand hours of computer time to crack by factoring, and may be considered "difficult," but not "bulletproof." A key of 1024 bits is currently considered "bulletproof` or impossible to crack; with the best available factorization techniques, it would require all global computing resources to be devoted to the task for many years. Even as computer calculation speed increases impressively, a small increase of the key size can preserve essentially absolute security of the private decoding key.
While perfect privacy may be desired by individual correspondents, there is occasionally a need for a legitimate monitoring authority to decode a message. Such authorities may include law enforcement agencies seeking evidence of criminal activity, employers seeking to investigate dissemination of trade secrets, and governments seeking to prevent espionage by the dissemination of national security secrets, including secret communications by terrorists into and out of the country. Thus, governments may limit the size of keys to ensure that decoding messages is merely difficult, but not impossible. Unfortunately, this means that users are vulnerable to decoding of their public keys and messages by the extraordinary efforts of unauthorized interceptors or "eavesdroppers". This is of particular concern as major financial transactions and sensitive technology may need to be transmitted electronically. Thus, there is a trade-off between privacy to protect efficient commerce, and decodability to ensure national security.
In current practice, there is no limit placed on the size of public keys used in domestic communications, but keys used for international communications are limited. U.S. law is believed currently to prohibit international transmission or receipt of a communication encoded with a public key greater than 512 bits in length. As a result, a commercially sensitive communication within a multinational company, but which crosses national borders, may be vulnerable to interception and decoding, or must be restricted to less efficient means of communication. If some communications are exempted from the key length limit, such as for international banking, an opportunity exists for international espionage or terrorist communications undetectable by government investigators.
Accordingly, there is a need for a method of encrypted communication including creating a message and looking up a public key of a recipient. Then, encoding the message via a first encoding process using a first portion of the public key to generated an intermediate encoded message. The intermediate encoded message is encoded via a second encoding process using a second portion of the public key to generate a final encoded message. Then, the final encoded message is sent to a recipient. The public key may have a first key portion, a second key portion, and a third key portion, with the third key portion containing the encoded identity of a data element needed to decode a message encoded with the second key portion. The third key portion is encoded with the public key of a monitoring authority to enable the monitoring authority to more readily decode transmitted messages.